// 大根堆
function buildHeap(arr, len) {
    if (len === 1) return
    for (let i = Math.floor(len / 2); i > 0; i--) {
        heapify(arr, len, i)
    }
}
function heapify(arr, len, i) {
    while (true) {
        let minIndex = i
        if (2 * i <= len && arr[2 * i].val > arr[i].val) {
            minIndex = 2 * i
        }
        if (2 * i + 1 <= len && arr[2 * i + 1].val > arr[minIndex].val) {
            minIndex = 2 * i + 1
        }
        if (minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break;
        }
    }
}
function swap(arr, i, j) {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
    let m = {}
    for (let i = 0; i < nums.length; i++) {
        if (m[nums[i]]) m[nums[i]]++
        else m[nums[i]] = 1
    }
    let arr = [null]
    let count = 0
    Object.keys(m).forEach((val, key) => {
        if (count < k) {
            arr.push({
                val: val,
                key: key
            })
            if (count == k - 1) buildHeap(arr, k)
        } else if (arr[1].val < val) {
            arr[1] = {
                val: val,
                key: key
            }
            heapify(arr, k, 1)
        }
    })
    buildHeap(arr, arr.length - 1)
    let i = arr.length - 1
    let ans = []
    while (i >= arr.length - k) {
        ans.push(arr[1])
        swap(arr, 1, i)
        heapify(arr, i - 1, 1)
        i--
    }
    return ans
};